This paper introduces anew onlineestimator ofentropy-regularized OTdistances between twosucharbitrary distributions.

Optimal Transport (OT) distances are now routinely used as loss functions in ML tasks.

We first introduce two useful known lemmas, and prove the propositions in their order of appearance. We refer the reader to the original references for proofs. We will also need a uniform law of large numbers for functions. The following lemma is a consequence of Example 19.7 and Lemma 19.36 of V an der V aart (2000), and is copied in Lemma B.6 in We use Theorem 1 from Diaconis and Freedman (1999). We then turn to prove Proposition 2. A.3.1 Noise-free online Sinkhorn Proposition 5. Proof of Proposition 2. For discrete realizations ˆ α and ˆ β, we define the perturbation terms ε From Eq. (8), for all t > 0, we have 0 null e Following the derivations of Moulines and Bach (2011, Theorem 2), we have the following bias-variance decomposed upper-bound, provided that 0 null a < 1 and a + b > 1 .

We thank the reviewers for their insightful comments. We address their interrogations and comments below. We will better motivate our work. We may consider the output of a trained CNN on CIFAR10 images. It is of course higher for batch method than online method.

Optimal Transport (OT) distances are now routinely used as loss functions in ML tasks. This paper introduces a new online estimator of entropy-regularized OT distances between two such arbitrary distributions. It uses streams of samples from both distributions to iteratively enrich a non-parametric representation of the transportation plan. Compared to the classic Sinkhorn algorithm, our method leverages new samples at each iteration, which enables a consistent estimation of the true regularized OT distance. We provide a theoretical analysis of the convergence of the online Sinkhorn algorithm, showing a nearly-1/n asymptotic sample complexity for the iterate sequence.

Optimal Transport (OT) distances are now routinely used as loss functions in ML tasks. Yet, computing OT distances between arbitrary (i.e. not necessarily discrete) probability distributions remains an open problem. This paper introduces a new online estimator of entropy-regularized OT distances between two such arbitrary distributions. It uses streams of samples from both distributions to iteratively enrich a non-parametric representation of the transportation plan. Compared to the classic Sinkhorn algorithm, our method leverages new samples at each iteration, which enables a consistent estimation of the true regularized OT distance. We cast our algorithm as a block-convex mirror descent in the space of positive distributions, and provide a theoretical analysis of its convergence. We numerically illustrate the performance of our method in comparison with concurrent approaches.